package leetcode101.dynamic_planning;

import java.util.Arrays;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code18
 * @Description 回文数变换
 * 所谓回文数就是一个数字，从左边读和右边读都是一样的结果，例如: 123321
 * 现在有一个只包含1、2、3、4的数字，你可以通过在任意位置增加一位数字或删除一位数字
 * 你可以通过在任意位置增加一位数字或者删除一位数字将其变换成一个回文数。但是增加删除不同数字所需要的代价是不一样的
 * 已知增加和删除每个数字的代价如下：
 *      增加这个数字的代价   删除这个数字的代价
 * 1    100               120
 * 2    200               350
 * 3    360               200
 * 4    220               320
 * 请问如何通过最少的代价将一个数字变成一个回文数，当然如果一个数字本身已经是一个回文数的话，那么变化代价为0
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-04-17 15:24
 */
public class Code18 {

    public static void main(String[] args) {
        int[] arr1 = new int[]{2, 2, 2, 2};
        int[] arr2 = new int[]{1, 2, 3, 4};
        int[] arr3 = new int[]{1, 2, 3, 2, 2};
        System.out.println(Arrays.toString(arr1));
        System.out.println(palindromicTransformation(arr1));
        System.out.println(Arrays.toString(arr2));
        System.out.println(palindromicTransformation(arr2));
        System.out.println(Arrays.toString(arr3));
        System.out.println(palindromicTransformation(arr3));
    }

    public static int[][] costs = new int[][] {{1, 100, 120}, {2, 200, 350}, {3, 360, 200}, {4, 220, 320}};

    public static int palindromicTransformation(int[] arr) {
        int n = arr.length;
        int[] nums1;
        int[] nums2;
        if ((n & 1) == 0) { // 分奇偶构造两个数组
            nums1 = Arrays.copyOfRange(arr, 0, (n >> 1));
            nums2 = Arrays.copyOfRange(arr, (n >> 1), n);
        } else {
            nums1 = Arrays.copyOfRange(arr, 0, (n >> 1));
            nums2 = Arrays.copyOfRange(arr, (n >> 1) + 1, n);
        }

        for (int i = 0; i < nums2.length >> 1; i++) { // 反转其中一个
            int temp = nums2[i];
            nums2[i] = nums2[nums2.length - 1 - i];
            nums2[nums2.length - 1 - i] = temp;
        }
        
        int[][] dp = new int[(n >> 1) + 1][(n >> 1) + 1]; // 动态规划

        for (int i = 1; i < dp.length; i++) { // 要点 要选择添加一个和删除一个中的最小值
            dp[i][0] = Math.min(costs[nums1[i - 1] - 1][1], costs[nums1[i - 1] - 1][2]);
        }

        for (int i = 1; i < dp[0].length; i++) { // 要点 要选择添加一个和删除一个中的最小值
            dp[0][i] = Math.min(costs[nums2[i - 1] - 1][1], costs[nums2[i - 1] - 1][2]);
        }

        for (int i = 1; i < dp.length; i++) {
            for (int j = 1; j < dp[0].length; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    dp[i][j] = Math.min(
                            Math.min(
                                    Math.min(
                                            dp[i][j - 1] + costs[nums2[j - 1] - 1][1], // 填一个4
                                            dp[i][j - 1] + costs[nums2[j - 1] - 1][2] // 删除一个4
                                    ),
                                    dp[i - 1][j] + costs[nums1[i - 1] - 1][1] // 填一个1
                            ),
                            dp[i - 1][j] + costs[nums1[i - 1] - 1][2] // 删除一个1
                    );
                }
            }
        }
        return dp[(n >> 1)][(n >> 1)];
    }
}
/*
这道题属于LeetCode72的变形题
本质都是编辑距离
首先将数组划分成左半边的数组nums1[] 右半边的数组nums2[]
然后要做的就是通过编辑距离将nums1[] 以花费最小代价的前提下变成nums2[]的反转
然后就是填dp表格
dp[i][j] 代表了将nums1[i - 1] 变成一样 nums2[j - 1]的最小花费那么分为两种情况：
如果nums1[i - 1] = nums2[j - 1] 的话那么不用调整，dp[i][j] = dp[i - 1][j - 1]
如果nums1[i - 1] != nums2[j - 1] 的话那么需要从以下情况中挑选一个最小值填上即可
dp[i - 1][j] + 从第一个数组中删除第 nums1[i - 1] 的花费
dp[i - 1][j] + 从第二个数组中增加nums1[i - 1] 的花费
dp[i][j - 1] + 从第一个数组中删除第 nums2[j - 1] 的花费
dp[i][j - 1] + 从第二个数组中增加nums2[j - 1] 的花费
 */